package com.demo.java.OD201_250.OD207;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【计算疫情扩散时间 病菌感染】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145907062
 */
public class OdMain {

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            String content = scanner.nextLine();  // 输入地图
            if (!content.contains("1")) {  // 如果没有感染区，直接输出-1
                System.out.println(-1);
                return;
            }
            solveProblem(content);  // 解决问题
        }
    }

    private static void solveProblem(String mapString) {
        String[] map = mapString.split(",");
        int n = (int) Math.sqrt(map.length);  // 计算地图的大小

        // 将字符串转化为二维数组表示地图
        int[][] mapGrid = new int[n][n];
        int k = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; j++) {
                mapGrid[i][j] = Integer.parseInt(map[k++]);
            }
        }

        int day = 0;

        // 每天模拟病毒扩散
        while (isMapNotInfected(mapGrid)) {
            infectAll(mapGrid);  // 扩散病毒
            day++;
        }

        // 如果一开始地图就没有感染区域，返回-1
        System.out.println(day == 0 ? -1 : day);
    }

    // 扩散病毒
    private static void infectAll(int[][] mapGrid) {
        int n = mapGrid.length;
        ArrayList<int[]> virus = new ArrayList<>();
        // 找到所有已感染的区域
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; j++) {
                if (mapGrid[i][j] == 1) {
                    virus.add(new int[]{i, j});
                }
            }
        }

        // 四个方向的邻居
        int[][] positions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        // 对于每个已感染的区域，向四个方向扩散
        for (int[] virusPos : virus) {
            int x = virusPos[0];
            int y = virusPos[1];
            for (int[] p : positions) {
                int x1 = Math.min(n - 1, Math.max(x + p[0], 0));
                int y1 = Math.min(n - 1, Math.max(y + p[1], 0));
                mapGrid[x1][y1] = 1;
            }
        }
    }

    // 判断是否所有区域都已感染
    private static boolean isMapNotInfected(int[][] mapGrid) {
        int n = mapGrid.length;
        for (int[] row : mapGrid) {
            for (int j = 0; j < n; j++) {
                if (row[j] == 0) {
                    return true;  // 如果还有未感染区域，返回true
                }
            }
        }
        return false;  // 如果没有未感染区域，返回false
    }
}